//有效数独
class Solution {
    bool row[9][10],col[9][10],grid[3][3][10];
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        return dfs(board);
    }

    bool dfs(vector<vector<char>>& b)
    {
        for(int i = 0; i < b.size(); i++)
        {
            for(int j = 0; j < b[0].size(); j++)
            {
                if(b[i][j] != '.')
                {
                    int num = b[i][j] - '0';
                    if(row[i][num] || col[j][num] || grid[i/3][j/3][num])
                        return false;
                    else
                    {
                        row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                    }
                }
            }
        }
        return true;
    }
};


//解数独
class Solution {
    bool row[9][10], col[9][10], grid[3][3][10];
public:
    void solveSudoku(vector<vector<char>>& board) {
        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++)
            {
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        dfs(board,0,0);
    }

    bool dfs(vector<vector<char>>& b,int x,int y)
    {
        if(x == 9)
            return true;
        if(y == 9)
            return dfs(b,x+1,0);

        if(b[x][y] != '.')
            return dfs(b,x,y + 1);

        if(b[x][y] == '.')
        for(int i = 1; i <= 9; i++)
        {
            if(!row[x][i] && !col[y][i] && !grid[x / 3][y / 3][i])
            {
                row[x][i] = col[y][i] = grid[x / 3][y / 3][i] = true;
                b[x][y] = i + '0';
                if(dfs(b, x, y + 1)) return true;
                b[x][y] = '.';
                row[x][i] = col[y][i] = grid[x / 3][y / 3][i] = false;
            }
        }
        return false;
    }
};

class Solution {
    bool row[9][10], col[9][10], grid[3][3][10];
public:
    void solveSudoku(vector<vector<char>>& board) {
        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++)
            {
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        dfs(board);
    }

    bool dfs(vector<vector<char>>& b)
    {
        for(int x = 0; x < 9; x++)
            for(int y = 0; y < 9; y++)
            {
                if(b[x][y] == '.')
                {
                    for(int num = 1; num <= 9; num++)
                    {
                        if(!row[x][num] && !col[y][num] && !grid[x / 3][y / 3][num])
                        {
                            row[x][num] = col[y][num] = grid[x / 3][y / 3][num] = true;
                            b[x][y] = num + '0';
                            if(dfs(b))  return true;
                            row[x][num] = col[y][num] = grid[x / 3][y / 3][num] = false;
                            b[x][y] = '.';
                        }
                    }
                    
                    return false;
                }
            }
            return true;
    }
};
